package algorithm.状态压缩的动态规划;

/*
* 给定一个整数 maxChoosableInteger （整数池中可选择的最大数）和另一个整数 desiredTotal（累计和）
判断先出手的玩家是否能稳赢（假设两位玩家游戏时都表现最佳）
https://leetcode.cn/problems/can-i-win/
*
* */
public class CanIWin {

    public static boolean canIWin0(int maxChoosableInteger, int desiredTotal) {
        if(desiredTotal == 0)
            return true;
        if((maxChoosableInteger + 1) * maxChoosableInteger >> 1 < desiredTotal)
            return false;
        int[] arr = new int[maxChoosableInteger + 1];
        return process0(arr, desiredTotal);
    }


    //先手
    public static boolean process0(int[] arr, int rest){
        if(rest <= 0)
            return false;

        for (int i = 1; i < arr.length; i++) {
            if(arr[i] != 1){
                arr[i] = 1;
                boolean result = process0(arr, rest - i);
                arr[i] = 0;
                if(!result){
                    return true;
                }
            }
        }
        return false;
    }


    public static boolean canIWin1(int maxChoosableInteger, int desiredTotal) {
        if(desiredTotal == 0)
            return true;
        if((maxChoosableInteger + 1) * maxChoosableInteger >> 1 < desiredTotal)
            return false;
        int length = (1 << maxChoosableInteger + 1) - 2;
        int[] dp = new int[length + 1];
        return process1(maxChoosableInteger, 0, desiredTotal, dp);
    }

    public static boolean process1(int maxChoosableInteger, int status, int rest,  int[] dp){
        if(dp[status] != 0)
            return dp[status] == 1;

        if(rest <=  0)
            return false;

        for (int i = 1; i < maxChoosableInteger + 1; i++) {
            if((status & (1 << i)) == 0){
                status = status | (1 << i);
                boolean b = process1(maxChoosableInteger, status, rest - i, dp);
                status = status ^ (1 << i);
                if(!b){
                    dp[status] = 1;
                    return true;
                }
            }
        }
        dp[status] = -1;
        return false;
    }

    public static void main(String[] args) {
        System.out.println(canIWin0(5, 50));
    }







}
